/*
 * @Author: szx
 * @Date: 2022-05-25 15:07:11
 * @LastEditTime: 2022-05-25 16:34:51
 * @Description:
 * @FilePath: \leetcode\面试题\10\03\03.js
 */
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var search = function (arr, target) {
    return arr.findIndex((v, i) => v == target);
};
// var search = function (arr, target) {
//     const a0 = arr[0];
//     let i = 0,
//         j = arr.length - 1;
//     while (i <= j) {
//         const mid = (i + j) >> 1;
//         if (target >= a0) {
//             if (arr[mid] > target || (arr[mid] == a0 && a0 == arr[arr.length - 1]) || arr[mid] < a0) j = mid - 1;
//             else i = mid + 1;
//         } else {
//             if (arr[mid] >= a0 || arr[mid] < target) i = mid + 1;
//             else j = mid - 1;
//         }
//         console.log(i, j, mid);
//     }
//     return -1;
// };

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var search = function (arr, target) {
    if (arr[0] == target) return 0;
    let i = 0,
        j = arr.length - 1;
    while (i <= j) {
        let mid = (i + j) >> 1;
        if (arr[mid] == target) {
            while (mid > 0 && arr[mid - 1] == arr[mid]) mid--;
            return mid;
        }
        if (arr[mid] < arr[j]) {
            if (arr[mid] < target && target <= arr[j]) i = mid + 1;
            else j = mid - 1;
        } else if (arr[mid] > arr[j]) {
            if (arr[i] <= target && target < arr[mid]) j = mid - 1;
            else i = mid + 1;
        } else {
            j--;
        }
    }
    return -1;
};

var search = function (arr, target) {
    let i = 0,
        j = arr.length - 1;
    while (j > 0 && arr[i] == arr[j]) j--;
    // 然后找到那个跳变的左边界
    while (i <= j) {
        const mid = (i + j) >> 1;
        if (arr[mid] >= arr[0]) i = mid + 1;
        else j = mid - 1;
    }
    // 判断目标是在左线段还是右线段
    if (target >= arr[0]) i = 0;
    else j = arr.length - 1;
    // 常规二分查找，找到左边界
    while (i <= j) {
        const mid = (i + j) >> 1;
        if (arr[mid] < target) i = mid + 1;
        else j = mid - 1;
    }
    return arr[i] == target ? i : -1;
};

const ar = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14];

// for (let i of ar) {
//     console.log(search(ar, i));
// }
// console.log(search(ar, 0));

// console.log(search([1, 1, 1, 1, 1, 2, 1, 1, 1], 2));
console.log(search([1, -2], -2));
